package demo1;

import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op : ops) {
            m = Math.min(m, op[0]);
            n = Math.min(n, op[1]);
        }
        return m * n;
    }

    public int maxSizeSlices(int[] nums) {
        int n = nums.length, m = n/3;
        int[][] dp1 = new int[n+1][m+1];
        int[][] dp2 = new int[n+1][m+1];
        for(int i = 0; i < n-1; ++i){
            for(int j = 1; j <= m; ++j){
                dp1[i+2][j] = Math.max(dp1[i+1][j], dp1[i][j-1] + nums[i]);
                dp2[i+2][j] = Math.max(dp2[i+1][j], dp2[i][j-1] + nums[i+1]);
            }
        }
        return Math.max(dp1[n][m], dp2[n][m]);
    }

    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        double[] time = new double[n];
        Map<Integer,Double> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            time[i] = (target - position[i])/(double)speed[i];
            map.put(position[i], time[i]);
        }
        Arrays.sort(position);
        Deque<Double> stack = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && map.get(position[i]) >= stack.peek()){
                stack.pop();
            }
            stack.push(map.get(position[i]));
        }
        return stack.size();
    }
}
